package basic.sort.tree;

import basic.sort.utils.NodeUtil;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.tree
 * @since JDK1.8
 *
 * 判断一颗树是否是平衡二叉树
 */
public class IsBalanced {

    public static boolean isBalanced1(NodeUtil head) {
        boolean[] ans = new boolean[1];
        ans[0] = true;
        process1(head, ans);
        return ans[0];
    }

    public static int process1(NodeUtil head, boolean[] ans) {
        if (!ans[0] || head == null) {
            return -1;
        }
        int leftHeight = process1(head.left, ans);
        int rightHeight = process1(head.right, ans);
        if (Math.abs(leftHeight - rightHeight) > 1) {
            ans[0] = false;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }

    private static boolean isBalanced2(NodeUtil head) {
        return process(head).isBalanced;
    }

    /**
     * 记录二叉树的基本信息：是否是平衡的与高度
     */
    private static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean b, int h) {
            isBalanced = b;
            height = h;
        }
    }
    
    private static Info process(NodeUtil head) {
        if (head == null) {
            return new Info(true, 0);
        }

        // 获取左右子树的信息
        Info left = process(head.left);
        Info right = process(head.right);

        // 处理信息
        // 获取自身高度
        int height = Math.max(left.height, right.height) + 1;
        // 临时变量
        boolean isBalanced = true;
        // 判断此节点是否是平衡的
        if (!left.isBalanced || !right.isBalanced || Math.abs(left.height - right.height) >= 2) {
            isBalanced = false;
        }

        return new Info(isBalanced, height);
    }
    
    public static NodeUtil generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }
    
    public static NodeUtil generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        NodeUtil head = new NodeUtil((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    public static void main(String[] args) {
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            NodeUtil head = generateRandomBST(maxLevel, maxValue);
            if (isBalanced1(head) != isBalanced2(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
}
